package leetcode.weekly.week336;

import java.util.Arrays;

//Solution4Test
public class Solution4 {

	public int findMinimumTime(int[][] tasks) {
		Arrays.sort(tasks, (a, b) -> a[1] != b[1] ? a[1] - b[1] : a[0] - b[0]);
		boolean[] have = new boolean[2001];
		len = 2005;
		arr = new int[len];
		for (int i = 0; i < tasks.length; i++) {
			int[] t = tasks[i];
			int st = t[0], en = t[1], du = t[2];
			int exist = find(st, en);
			int rest = du - exist;
			for (int j = en; j >= st && rest > 0; j--) {
				if (!have[j]) {
					have[j] = true;
					rest--;
					add(j);
				}
			}
		}

		int ans = 0;
		for (int i = 0; i < have.length; i++) {
			ans += have[i] ? 1 : 0;
		}
		return ans;
	}

	private int find(int st, int en) {
		return this.query(en) - this.query(st - 1);
	}

	int len;
	int[] arr;

	public void add(int num) {
		while (num < len) {
			arr[num]++;
			num += this.lowbit(num);
		}
	}

	public void sub(int num) {
		while (num < len) {
			arr[num]--;
			num += this.lowbit(num);
		}
	}

	public int query(int num) {
		int ans = 0;
		while (num > 0) {
			ans += arr[num];
			num -= this.lowbit(num);
		}
		return ans;
	}


	public int lowbit(int num) {
		return num & -num;
	}

}
